/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/range-sum-query-mutable
   @Language: C++
   @Datetime: 19-05-08 11:38
   */

// Method 1, Binary Indexed Tree, Time 441ms
class NumArray {
	vector<int> nums, bits;
public:
	NumArray(vector<int> &nums) {
		this->nums=vector<int>(nums.size(),0);
		bits = vector<int>(nums.size()+1,0);
		for(int i=0; i<nums.size(); ++i)
			update(i,nums[i]);
	}

	void update(int k, int val) {
		for(int i=k+1; i<=nums.size(); i+=i&(-i))
			bits[i]+=val-nums[k];
		nums[k]=val;
	}

	int sumRange(int i, int j) {
		int sum=0;
		for(++j; j>0; j-=j&(-j))
			sum+=bits[j];
		for(i; i>0; i-=i&(-i))
			sum-=bits[i];
		return sum;
	}
};


// Method 2, Segment Tree, Time 308ms
class NumArray {
	struct SegmentTreeNode{
		int start, end;
		int val;
		SegmentTreeNode *left, *right;
		SegmentTreeNode(int start, int end, int val){
			this->start=start;
			this->end=end;
			this->val=val;
			this->left=this->right=NULL;
		}
	};
	SegmentTreeNode *m_root;

	SegmentTreeNode *build(vector<int> &A, int start, int end){
		if(A.size()<1 || start>end) return NULL;
		SegmentTreeNode *root=new SegmentTreeNode(start, end, A[start]);
		if(start==end) return root;
		root->left=build(A,start,(start+end)/2);
		root->right=build(A,(start+end)/2+1,end);
		root->val=root->left->val+root->right->val;
		return root;
	}
	int query(SegmentTreeNode *root, int start, int end) {
		if(root==NULL || start>root->end || end<root->start) return 0;
		if(start==root->start && end==root->end) return root->val;
		int mid=(root->start+root->end)/2;
		if(start>mid) return query(root->right,start,end);
		if(end<=mid) return query(root->left,start,end);
		return query(root->left,start,mid)+query(root->right,mid+1,end);
	}
	void modify(SegmentTreeNode *root, int index, int value) {
		if(root==NULL || index>root->end || index<root->start) return;
		if(root->start==index && root->end==index){
			root->val=value;
			return;
		}
		modify(root->left,index,value);
		modify(root->right,index,value);
		root->val=root->left->val+root->right->val;
	}
	void destroy(SegmentTreeNode *root){
		if(root==NULL) return;
		destroy(root->left);
		destroy(root->right);
		delete root;
	}
public:
	NumArray(vector<int> &nums) {
		m_root = build(nums,0,nums.size()-1);
	}
	
	void update(int k, int val) {
		modify(m_root,k,val);
	}
	
	int sumRange(int i, int j) {
		return query(m_root,i,j);
	}
};


/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
